package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
 *  * @date: 2021/3/9 23:55
 *  Question 16
 * @version: 1.0
 */
public class Q16_Merge2ListNode {

    public static void main(String[] args) {
        ListNode list1=new ListNode(3);
        list1.next=new ListNode(8);
        list1.next.next=new ListNode(9);
        list1.next.next.next=new ListNode(13);
        list1.next.next.next.next=new ListNode(16);
        list1.next.next.next.next.next=new ListNode(18);

        ListNode list2=new ListNode(6);
        list2.next=new ListNode(8);
        list2.next.next=new ListNode(9);
        list2.next.next.next=new ListNode(10);
        list2.next.next.next.next=new ListNode(12);
        list2.next.next.next.next.next=new ListNode(15);

        ListNode resultNode=mergeListNode(list1,list2);
        System.out.println("");
    }

    public static ListNode mergeListNode(ListNode list1,ListNode list2){
        ListNode megerNodes=null;
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        if (list1.data<=list2.data){
            megerNodes=list1;
            megerNodes.next=mergeListNode(list1.next,list2);
        }else {
            megerNodes=list2;
            megerNodes.next=mergeListNode(list1,list2.next);
        }
        return megerNodes;
    }


    private static class ListNode{
        int data;
        ListNode next;
        public ListNode(int data) {
            this.data = data;
        }
    }
}
